package LeetCode.BinarySearch;

/**
 * @author : LdLtd
 * @Date : 2023/7/14
 * @Description:寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class median_of_two_sorted_arrays {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = new int[]{};
        int[] nums2 = new int[]{2};
        System.out.println(solution.findMedianSortedArrays3(nums1, nums2));

    }

    static class Solution {
        //朴素解法，归并到一个数组，时间复杂度M+N,空间复杂度m+n
        public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
            int[] tem;
            int m = nums1.length;
            int n = nums2.length;
            tem = new int[m + n];
            if (m == 0) {
                return (nums2[(n + 1) / 2] + nums2[n / 2 + 1]) / 2;
            }
            if (n == 0) {
                return (nums1[(m + 1) / 2] + nums1[n / 2 + 1]) / 2;
            }
            int count = 0, i = 0, j = 0;
            while (count != m + n) {
                if (i == m) {
                    while (j != n) {
                        tem[count++] = nums2[j++];
                    }
                    break;
                }
                if (j == n) {
                    while (i != m) {
                        tem[count++] = nums1[i++];
                    }
                    break;
                }
                if (nums1[i] < nums2[j]) {
                    tem[count++] = nums1[i++];
                } else {
                    tem[count++] = nums2[j++];
                }
            }
            return (tem[(count + 1) / 2 - 1] + tem[count / 2]) / 2;
        }


        /*不开辟空间
         * 需要第（m+n+1）/2 -1和(m+n)/2个数
         * 时间复杂度依旧是 O(m+n)O(m+n)。
         * 空间复杂度是 O(1）O(1）
         * */
        public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int len = m + n;
            //奇数，直接返回res，t保存上一个位置的结果
            int res = -1, t = -1;
            //记录两个数组运行到的位置
            int a = 0, b = 0;
            //遍历到中间的位置
            for (int i = 0; i <= len / 2; i++) {
                t = res;
                if (a < m && (b >= n || nums1[a] < nums2[b])) {
                    res = nums1[a++];
                } else {
                   res = nums2[b++];
                }
            }
            if ((len & 1) == 0) {
                return (t + res) / 2.0;
            } else {
                return res;
            }
        }
/*
* 时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n）O(log(m+n）。
空间复杂度： O(1)。
* 我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 3个数字，
* 上边数组中的 4 和下边数组中的 3，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。
* 为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，
* 把小的那个对应的数组的数字排除，将两个新数组进入递归，
* 并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。

*/
        public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int len = m + n;
            int l=(len+1)/2;
            int r=(len+2)/2;
            return (getKth(nums1,0,m-1,nums2,0,n-1,l)+getKth(nums1,0,m-1,nums2,0,n-1,r))*0.5;
        }
        private double getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){
            int len1=end1 - start1 +1;
            int len2 = end2 - start2+1;
            //让len1的长度始终小于len2，保证空的数组一定是len1
            if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);
            //空的时候
            if(len1==0) return nums2[start2+k-1];
            //最后的情况，终止条件
            if(k==1) return  Math.min(nums1[start1],nums2[start2]);
            //比较位置的数
            int i=start1+Math.min(len1,k/2)-1;
            int j=start2+Math.min(len2,k/2)-1;
            //排除掉小于的，那个数组的前面几个数
            if(nums1[i]>nums2[j]){
                return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
            }else {
                return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
            }
        }

    }
}